package com.ztl.leetcode.SwordFingerOffer;

/**
 * @author @ztl
 * @ClassName:ReverseLinkedList
 * @Package:com.ztl.leetcode.SwordFingerOffer
 * @date 2023年05月13日 17:15
 * @description: 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 * @version: 1.0
 */
public class ReverseLinkedList_24 {

    //仅需遍历一次链表，时间复杂度O(n),使用res和curr操作指针，空间复杂度O(1)
    public ListNode reverseList(ListNode head) {
        //借助额外的指针帮助完成链表反转，达到原地反转效果
        //思路：链表head从头到尾存放到链表res中；
        //而res把接收的节点从尾到头存放，最后返回res头节点即可

        //temp保存正序的节点，避免正序节点丢失

        //定义链表res用来存放返回结果，从尾到头存放
        //按照要求将返回链表res最后一个节点定义为null
        ListNode res = null;

        //curr指向当前操作节点，用改变节点指向到res链表
        ListNode curr = head;

        //越界判定
        while(curr!=null){
            //由于curr.next需要指向res，为防止原链表丢失；
            //需要使用额外的指针temp记录curr原来指向的next
            ListNode temp = curr.next;

            //根据上面思路，将当前节点指向res，达到反转链表效果
            curr.next = res;

            //此时curr指向res，res需要指向curr即从尾节点往前的一个节点
            res = curr;

            //此时curr需要指向temp即curr原来的next
            //可以理解为curr=curr.next
            curr = temp;
        }

        //最后返回反转完成的链表
        return res;
    }
}
